package 二叉树;

public class _110_平衡二叉树 {

	public boolean isBalanced(TreeNode root) {
		return balanced(root).isBlanace;

	}

	public class NewNode {
		int height;
		boolean isBlanace;

		public NewNode(int height, boolean isBlanace) {
			this.isBlanace = isBlanace;
			this.height = height;
		}
	}

	public NewNode balanced(TreeNode node) {
		if (node == null) {
			return new NewNode(0, true);
		}

		NewNode left = balanced(node.left);
		NewNode right = balanced(node.right);
		if (Math.abs(left.height - right.height) > 1 || !left.isBlanace || !right.isBlanace) {
			return new NewNode(0, false);
		} else {
			return new NewNode(Math.max(left.height, right.height) + 1, true);
		}
	}

	public boolean isBalanced2(TreeNode root) {
		if (root == null) {
			return true;
		} else {
			return Math.abs(height2(root.left) - height2(root.right)) <= 1 && isBalanced2(root.left)
					&& isBalanced2(root.right);
		}
	}

	private int height2(TreeNode node) {
		if (node == null) {
			return 0;
		} else {
			return Math.max(height2(node.left), height2(node.left)) + 1;
		}
	}

	public boolean isBalanced1(TreeNode root) {
		return height1(root) >= 0;
	}

	private int height1(TreeNode root) {
		if (root == null)
			return 0;
		int lh = height1(root.left), rh = height1(root.right);
		if (lh >= 0 && rh >= 0 && Math.abs(lh - rh) <= 1) {
			return Math.max(lh, rh) + 1;
		} else {
			return -1;
		}
	}
}